package org.leetcode.middle.leetcode763;

import java.util.*;

public class Solution {

    public List<Integer> partitionLabels5(String s) {
        List<Integer> res = new ArrayList<>();
        int n =s.length();
        HashMap<Character,Integer> hashMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            hashMap.put(s.charAt(i),i);
        }

        int start =0;
        int end =0;

        for (int i = 0; i < n; i++) {
            end= Math.max(end,hashMap.get(s.charAt(i)));
            if (i==end){
                res.add(end-start+1);
                start=end+1;
            }
        }


        return res;
    }

    public List<Integer> partitionLabels3(String s){

        List<Integer> res = new ArrayList<>();
        Map<Character,Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            //用来统计每个字符串的最后出现的位置
            map.put(s.charAt(i),i);
        }
        int start=0;
        int end =0;

        for (int i = 0; i < s.length(); i++) {
            //确保当前的片段的end包含了当前片段的所有字符
            end =Math.max(end,map.get(s.charAt(i)));
            //当前的下标到达了end
            if (i==end){
                res.add(end-start+1);
                start=end+1;
            }
        }
        return res;
    }
    public List<Integer> partitionLabels(String s)
    {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            edge[chars[i] - 'a'] = i;
        }
        int idx = 0;
        int last = -1;
        for (int i = 0; i < chars.length; i++) {
            idx = Math.max(idx,edge[chars[i] - 'a']);
            if (i == idx) {
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }

    public List<Integer> partitionLabels2(String s)
    {
        List<Integer> list = new LinkedList<>();
        Map<Character,Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i),i);
        }

        int end =0;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            end=Math.max(end,map.get(s.charAt(i)));

            if (i==end)
            {
                list.add(end-start+1);
                start=end+1;
            }

        }


        return list;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> list = solution.partitionLabels2("ababcbacadefegdehijhklij");

        System.out.println(list);
    }
}
